1. Field of the Present Invention
The present invention generally relates to the field of digital circuits and more particularly to a circuit for adding multiple vectors.
2. History of Related Art
In VLSI design, occasions frequently arise in which the sum of multiple binary vectors is required such as in the alignment of operands for multiply-add instructions. Frequently, the sum generated by such an operation is used to steer data. As processor speeds increase into and beyond 1 GHz, it becomes highly desirable to generate the necessary sum with a minimum of delay. Typically, however, adder circuits are designed for use with only a pair of input vectors. If the number of input vectors increases, a performance penalty is paid to incorporate the additional operands into the final result. In addition, these circuits typically implement multiple xe2x80x9cverticalxe2x80x9d levels of logic to generate a result. Each level of logic adds delay to the time required to generate a result. In addition, traditional adder circuits typically produce a binary encoded result that must be manipulated before it can be used as the select signal suitable for steering data. Therefore it would be highly desirable to implement a circuit for computing a multiple vector summation with a delay that does not increase significantly with the number of input vectors. Moreover, it would be desirable if the implemented solution generated a result that was suitable for use with a multiplexer or other selection circuitry.
The problems identified above are in large part addressed by a method and calculation circuit suitable for adding multiple binary vectors. The method includes receiving a set of input vectors and generating a set of decoded summation vectors. Each of the set of decoded summation vectors indicates the value of at least a portion of the vector sum. The method further includes generating a set of decoded carry vectors. Each carry vector is used to select the summation vector for an adjacent portion of the vector sum from a set of preliminary vectors. In one embodiment, the method further includes counting the number of high bits in each bit position of the input vectors and generating decoded high bit vectors based upon the counting to facilitate the generation of decoded summation vectors. In one embodiment, the set of preliminary vectors includes an initial preliminary summation vector. In another embodiment, the invention contemplates a method of adding multiple binary vectors in which a first decoded summation vector indicative of a first portion of a vector sum is generated and a first decoded carry vector indicative of the carry from a first portion of the vector sum is generated. An initial second decoded summation vector corresponding to a second portion of the vector sum is then generated and a set of preliminary summation vectors generated from the initial second summation vector. Each of the preliminary summation vectors is rotated by one bit position from adjacent vectors in the set of preliminary summation vectors. One of the set of preliminary summation vectors is then selected as the second summation vector based upon the value of the first carry vector. In one embodiment, the value indicated by the first carry vector indicates the number of times the selected second summation vector was rotated from the initial summation vector. The method may further include selecting a second carry vector from a set of preliminary second carry vectors with the first carry vector.